1. Technical Field
This invention relates to image understanding machines and, more particularly, to computer architectures capable of both arithmetic or iconic and symbolic processing of image data.
2. Description of Related Art
There exists a need for a computer system that is capable of both arithmetic or iconic and symbolic processing of image data which is designed specifically for use in computer vision research and analyses efforts. Such a system can be used in a variety of different applications such as for use in real time processing of data from radar, infrared and visible sensors in areas such as aircraft navigation and reconnaissance. Another application of such a machine would be as a development system for use in vision laboratories in the implementation and simulation of many computationally intensive algorithms.
Machines which are capable of operating on image data (as compared to merely arithmetic data) are referred to alternatively as image processors, vision computers, image understanding machines and the like. Image understanding machines are sometimes thought of as a higher level machine than an image processor which is typically referred to as a machine for enhancing and classifying images whereas an image understanding machine involves the automatic transformation of the image to symbolic form, effectively providing a high level description of the image in terms of objects, their attributes, and their relationship to other objects in the image. The present invention is directed to this latter type of machine (although it can do the lower level tasks as well) and shall be referred to as an image understanding machine (IUM).
It is generally recognized that a high level IUM must be capable of performing two basic types of computations: arithmetic or iconic processing and symbolic manipulation. At this point in time it is not possible to give with certainty a detailed algorithmic specification for a general vision interpretation system. However, it would be desirable to provide an IUM that is capable of performing a number of visual information processing algorithms such as those listed in the following Table I.
TABLE I ______________________________________ A. LOW LEVEL VISION Edge Detection Differentiation Edge fitting Template matching Convolution Transform methods Histogramming Thresholding Local segmentation B. MID LEVEL VISION Line and Curve Fitting Hough Transform Projection Graph search Segmentation Recursive segmentation Region growing Boundary tracing Inference of 3-D surfaces Stereo Shape from shading and shadows Motion analysis Shape analysis 2-D features Generalized cones Structures Projection, rotation Angles and transcendentals Hough-like parameter spaces Surfaces Graph operations Color constancy Surface interpolation Structure from motion Iterative least squares C. HIGH LEVEL VISION Object recognition Graph matching Relaxation labeling Line matching Constraint satisfaction Symbolic modeling and manipulation Geometric reasoning Scene inferences Analysis using contextual information Production systems ______________________________________
It should be noted that future algorithmic developments will be a continually and rapidly evolving activity resulting from changing applications, advances in sensor and solid state technologies, and the need for added intelligence to deal even more rapidly and effectively with ever increasing amounts of raw data.
Many of the known concurrent or parallel processing computer architectures are not specifically intended to be used for image understanding purposes. Other image processing systems also suffer from the inability to efficiently perform both numeric and symbolic computations. For example, some of the prior architectures do not lend themselves to efficiently execute various artificial intelligent techniques such as frames, rules and evidential reasoning, while at the same time being capable of efficiently doing more iconic related image processing algorithms. One of the major drawbacks in the prior computer architectures was that their designs generally necessitated the transfer of large amounts of data between a host computer and the special purpose vision computer. Unfortunately, the transfer of data and instructions in the known architectures resulted in relatively slow operational speed. It is, of course, one of the ultimate objectives in any computer system to increase the speed of operation without unduly increasing costs or complexity of operation.
In performing some higher level vision processing techniques, it becomes necessary to apply unique labels to regions of contiguous pixels having the same value. For a binary image the pixels are either 0's (background) or 1's (data). Each region is defined as a group of contiguous pixels having the value of 1, i.e., each pixel in the region is connected to a neighboring pixel that also has a value of 1. These regions often represent objects of interest in the scene. In order for the image understanding machine to extract these regions for further processing, each individual region should be assigned its own identification code or label. One of the purposes of the present invention is to provide a technique for applying these labels to the regions very quickly so that the IUM can use these labels in further analyzing the regions.
It has been suggested to apply these labels to segmented image regions by the use of a diffusion process (i.e., label propagation) by logically resolving the collisions between adjacent pixels. The time it takes to logically propagate the labels is proportional to the image size and consequently, it is very slow for most images. The present invention, on the other hand, provides an improved architecture and method to apply unique region labels significantly faster.